package com.zy.tree.redblacktree;

/**
 * @author zhaoyi
 * @date 2021/9/26 15:10
 * 红黑树
 */
public class RedBlackTree {
    //根节点
    private Node root;


    /**
     * 插入
     * 简单点假设不会重复数据
     */
    public void put(int value) {
        root = put(root, value);
        root.isRed = false;
    }

    //删除操作
    public void delete(int value) {

    }





    private Node put(Node h, int value) {
        if (h == null) {
            return new Node(value, 1, true);
        }

        if (value > h.value) {
            //右边
            h.right = put(h.right, value);
        } else if (value < h.value) {
            //左边
            h.left = put(h.left, value);
        }

        //按图旋转
        if (isRed(h.right) && !isRed(h.left)) {
            h = rotateLeft(h);
        }
        if (isRed(h.left) && isRed(h.left.left)) {
            h = rotateRight(h);
        }
        if (isRed(h.left) && isRed(h.right)) {
            //两边都是红色变色
            flipColors(h);
        }
        h.count = 1 + size(h.left) + size(h.right);
        return h;
    }


    private boolean isRed(Node n) {
        return n != null && n.isRed;
    }


    //左旋
    private Node rotateLeft(Node h) {
        Node x = h.right;
        //x.isRed = false; 这样不对h原本可能也是红色的
        x.isRed = h.isRed;
        h.isRed = true;
        h.right = x.left;
        x.left = h;
        //子节点数量
        x.count = h.count;
        //node.count > 0 会直接返回所有不能用 size(h)
        h.count = 1 + size(h.left) + size(h.right);
        return x;
    }

    //右旋
    private Node rotateRight(Node h) {
        Node e = h.left;
        e.isRed = h.isRed;
        h.isRed = true;
        h.left = e.right;
        e.left = h;
        //子节点数量
        e.count = h.count;
        h.count = 1 + size(h.left) + size(h.right);
        return e;
    }

    /**
     * 变色
     * 保障黑平衡
     */
    private void flipColors(Node h) {
        h.isRed = true;
        if (h.left != null) {
            h.left.isRed = false;
        }
        if (h.right != null) {
            h.right.isRed = false;
        }
    }


    private int size(Node node) {
        if (node == null) {
            return 0;
        }
        if (node.count > 0) {
            return node.count;
        }

        return 1 + size(node.left) + size(node.right);
    }


}
